package com.hdu.other.dp.intervalDp;

import java.util.Arrays;

public class lc1547 {
    class Solution {
        public int minCost(int n, int[] cuts) {
            Arrays.sort(cuts);
            int len = cuts.length;
            int[] newCuts = new int[len + 2];
            newCuts[0] = 0;
            for (int i = 0; i < cuts.length; i++) {
                newCuts[i + 1] = cuts[i];
            }
            newCuts[len + 1] = n;
            int[][] dp = new int[len + 2][len + 2];
            for (int i = 0; i < len + 2; i++) {
                for (int j = 0; j < len + 2; j++) {
                    dp[i][j] = -1;
                }
            }
            return f(newCuts, 1, len, dp);
        }


        int f(int[] cuts, int l, int r, int[][] dp) {
            if (l > r) {
                return 0;
            }
            if (dp[l][r] != -1) {
                return dp[l][r];
            }
            int ans = Integer.MAX_VALUE;
            for (int i = l; i <= r; i++) {
                int curAns = f(cuts, l, i - 1, dp) + f(cuts, i + 1, r, dp);
                ans = Math.min(ans, curAns);
            }
            ans += cuts[r + 1] - cuts[l - 1];
            return dp[l][r] = ans;
        }
    }
}
